Most all technological undertakings can be understood and brought to fruition through mathematical analysis. Mathematical formulations and models of problems are used both to predict the outcome of an action and to infer the cause of an observation. Transform methods are often used to reduce the apparent complexity of these mathematical problems, and to take advantage of desirable properties of the restated problem. Everyday examples of very simple transformations include: converting from temperature measurement in degrees Fahrenheit to degrees Centigrade; and changing the description of a large circular groove, from center location and radius, to a chain of (x,y) coordinates so that a milling machine might be used to cut the groove.
Descriptions of complex systems (in fields as diverse as engineering, chemistry, biology, physiology, and economics) tend to give rise to differential equations, which in turn are often advantageously approached through the use of integral transforms. The more well-known integral transforms include the Fourier, Sine, Cosine, Laplace, Hankel, Hilbert, and Abel transforms. The Fourier Transform, for example, has the useful property of turning a convolution in the original function space into a multiplication in the transform domain: thus the behavior of an audio amplifier in response to an input signal, is more readily understood as the product of the signal spectrum and the amplifier frequency response (the transform of its time response), instead of the time convolution of the signal and amplifier transfer function.
Many data handling applications of commercial interest involve performing discrete transforms upon time dependent sequences of values at real-time rates. It is essential that the computation for an N-point transform be completed in less time than passes in the accumulation of another N-point collection of data. The decompression of transform-encoded video data streams, and the compression and decompression of audio signals are two prominent examples of applications wherein speed of transform computation has been of primary concern to designers. The general assumption of practitioners in the field has been that specialized, dedicated-function, electronic hardware must be utilized in such applications. Although it is well recognized that very high performance general computing platforms might provide the requisite speed, the high cost of such platforms prohibits the general utility of such an approach. Consequently, considerable effort has been expended on the reduction of hardware complexity.
U.S. Pat. No. 4,760,543 to Ligtenberg et al. is one such hardware implementation of a Discrete Cosine Transform (DCT hereinafter) with emphasis placed on the general simplification of the computations. U.S. Pat. No. 4,912,668 to Aubie et al. utilizes the regularity of the DCT algorithm disclosed by B. G. Lee in his paper entitled "A New Algorithm for the Discrete Cosine Transform", IEEE Transactions on Acoustics, Speech and Signal Processing, Vol. ASSP-32, pp. 1243-1245, Dec. 1984, in a direct hardware implementation of the calculations, to minimize the number of multipliers required.
U.S. Pat. No. 4,837,724 to Borgers et al. is an implementation derived from the DCT algorithms of W. Wang, and N. Suehiro and M. Hatori, with the higher complexity butterfly chains restated as sums of quadruples, thereby ensuring that no transform coefficient computation contained any chained multiplications. See the paper by N. Suehiro and M. Hatori entitled "Fast Algorithms for the DFT and Other Sinusoidal Transforms", IEEE Transactions on Acoustics, Speech and Signal Processing, Vol. ASSP-34, pp 642-644, June 1986. U.S. Pat. No. 4,831,574 to Duhamel essentially implements the B. G. Lee algorithm (1984), similar to Borgers, et al. but handles the required multiplications as serial arithmetic so as to avoid the explicit use of multipliers.
U.S. Pat. No. 4,849,922, to Riolfo performs a direct (forward only) DCT computation, wherein restriction to transform coefficient resolution of 8-bits, makes it possible to effect data multiplication using simple shifts and adds of the data values when forming the partial products of the transform. U.S. Pat. No. 4,449,194 to Wilhelm approximates the transform coefficients with 3-bit resolution to allow very simple shift and add implementation of a dedicated eight-point by eight-point DCT. U.S. Pat. No. 4,829,465 to Knauer et al. uses a scrambling of the input and output vectors (see the paper of B. G. Lee entitled "Input and Output Index Mappings for a Prime-Factor-Decomposed Computation of Discrete Cosine Transform", IEEE Transactions on Acoustics, Speech and Signal Processing, Vol. ASSP-37, pp. 237-244, Feb. 1989) to arrive at a transform matrix with symmetries which minimize the number of table entries which must be used for a table look-up approach to multiplication.
Accordingly, there is a need for a method whereby a general purpose computing device, such as comprises the central processing unit of common, small scale (so-called personal, portable, desktop, and so forth), computers, can perform discrete transform computations with adequate speed, so as to obviate the need for specialized electronic hardware, for many time-critical transform applications. One specific example of such a need is in connection with the real-time presentation of video image sequences which are retrieved in compressed form from a digital storage medium or a network communication medium.